package com.zhupf.heap;

import com.zhupf.part7.MergeTwoLists;

/**
 * @author zhupf
 * @date 2024年02月27日 15:18
 * @Description
 *
 *  215. 数组中的第K个最大元素
 */
public class FindKthLargest {


    public static void main(String[] args) {
        FindKthLargest findKthLargest = new FindKthLargest();
        int[] nums = {3,2,1,5,6,4};
        System.out.println(findKthLargest.findKthLargest(nums, 2));
    }


    public int findKthLargest(int[] nums, int k) {
        int[] heap = new int[k + 1];
        for (int i = 1; i < heap.length; i++) {
            heap[i] = nums[i - 1];
        }
        int len = heap.length;
        for (int i = len / 2; i > 0; i--) {
            minHeapify(heap, i, len);
        }
        for (int i = k; i < nums.length; i++) {
            if(nums[i] > heap[1]){
                heap[1] = nums[i];
                downHeapify(heap,1,len);
            }
        }
        return heap[1];

    }

    public void minHeapify(int[] heap, int parent, int len) {
        while ((parent * 2) < len) {
            int child = 2 * parent;
            if ((child + 1) < len && heap[child + 1] < heap[child]) {
                child = child + 1;
            }
            if (heap[child] < heap[parent]) {
                int tmp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = tmp;
                parent = child;
            } else {
                break;
            }
        }
    }

    public void downHeapify(int[] heap, int parent, int len) {
        int child = parent * 2;
        while (child < len) {
            if ((child + 1) < len && heap[child + 1] < heap[child]) {
                child = child + 1;
            }
            if (heap[parent] <= heap[child]) {
                break;
            }
            int tmp = heap[parent];
            heap[parent] = heap[child];
            heap[child] = tmp;
            parent = child;
            child = parent * 2;
        }
    }


}
